#include <stdio.h>

#define TemType int // 定义元素类型

// 定义顺序表结构体
typedef struct
{
    TemType *data; // 指向存储空间的指针
    int maxSize;   // 最大容量
    int length;    // 当前长度
} SeqList;

/*
 * 初始化顺序表
 * list: 指向顺序表的指针
 * size: 顺序表的最大容量
 */
void InitList(SeqList *list, int size)
{
    list->data = (TemType *)malloc(size * sizeof(TemType));
    if (list->data == NULL)
    {
        printf("Memory allocation failed\n");
        exit(1);
    }
    list->maxSize = size;
    list->length = 0;
}

/*
 * 销毁顺序表
 * list: 指向顺序表的指针
 */
void DestroyList(SeqList *list)
{
    free(list->data);
    list->data = NULL;
    list->maxSize = 0;
    list->length = 0;
}

/*
 * 让当前顺序表扩容
 * list: 指向顺序表的指针
 */
void ResizeList(SeqList *list)
{
    int newSize = list->maxSize * 2; // 新容量为当前容量的两倍
    TemType *newData = (TemType *)realloc(list->data, newSize * sizeof(TemType));
    if (newData == NULL)
    {
        printf("Memory reallocation failed\n");
        exit(1);
    }
    list->data = newData;
    list->maxSize = newSize;
}

/*
 * 让当前顺序表缩容
 * list: 指向顺序表的指针
 */
void ShrinkList(SeqList *list)
{
    if (list->length < list->maxSize / 4)
    {
        int newSize = list->maxSize / 2; // 新容量为当前容量的一半
        TemType *newData = (TemType *)realloc(list->data, newSize * sizeof(TemType));
        if (newData == NULL)
        {
            printf("Memory reallocation failed\n");
            exit(1);
        }
        list->data = newData;
        list->maxSize = newSize;
    }
}

/*
 * 在顺序表的指定位置插入元素
 * list: 指向顺序表的指针
 * pos: 插入位置（0-based）
 * value: 插入的元素值
 */
int InsertElem(SeqList *list, int pos, TemType value)
{
    if (pos < 0 || pos > list->length)
    {
        printf("Insertion position is invalid .\n");
        return 0; // 插入位置不合法或顺序表已满
    }

    if (list->length >= list->maxSize)
    {
        printf("List is full, resizing...\n");
        ResizeList(list); // 扩容
    }

    for (int i = list->length - 1; i >= pos; i--)
    {
        list->data[i + 1] = list->data[i]; // 元素后移
    }
    list->data[pos] = value; // 插入新元素
    list->length++;
    return 1; // 插入成功
}

/*
 * 头插入元素到顺序表
 * list: 指向顺序表的指针
 */
int InsertHead(SeqList *list, TemType value)
{
    return InsertElem(list, 0, value); // 头插入相当于在位置0插入
}

/*
 * 尾插入元素到顺序表
 * list: 指向顺序表的指针
 */
int InsertTail(SeqList *list, TemType value)
{
    return InsertElem(list, list->length, value); // 尾插入相当于在当前长度位置插入
}

/*
 * 删除顺序表的指定位置元素
 * list: 指向顺序表的指针
 * pos: 删除位置（0-based）
 */
int DeleteElem(SeqList *list, int pos)
{
    if (pos < 0 || pos >= list->length)
    {
        printf("Deletion position is invalid.\n");
        return 0; // 删除位置不合法
    }

    ShrinkList(list); // 判断是否缩容

    for (int i = pos; i < list->length - 1; i++)
    {
        list->data[i] = list->data[i + 1]; // 元素前移
    }
    list->length--;
    return 1; // 删除成功
}

/*
    * 替换顺序表的指定元素
    * list: 指向顺序表的指针
    * pos: 替换位置（0-based）
    * return: 返回1表示替换成功，0表示替换位置不合法
*/
int ReplaceElem(SeqList *list, int pos, TemType value)
{
    if (pos < 0 || pos >= list->length)
    {
        printf("Replacement position is invalid.\n");
        return 0; // 替换位置不合法
    }
    list->data[pos] = value; // 替换指定位置的元素
    return 1;                // 替换成功
}

/*
 * 清空顺序表
 * list: 指向顺序表的指针
 */
void ClearList(SeqList *list)
{
    list->length = 0; // 将长度置为0，清空顺序表
}

/*
 * 获取顺序表的指定位置元素
 * list: 指向顺序表的指针
 * pos: 获取位置（0-based）
 * return: 返回获取的元素值，若位置不合法则返回-1
 */
TemType GetElem(SeqList *list, int pos)
{
    if (pos < 0 || pos >= list->length)
    {
        printf("Get position is invalid.\n");
        return -1; // 获取位置不合法
    }
    return list->data[pos]; // 返回指定位置元素
}

/*
 * 打印顺序表的所有元素
 * list: 指向顺序表的指针
 */
void PrintList(SeqList *list)
{
    printf("List elements: ");
    for (int i = 0; i < list->length; i++)
    {
        printf("%d ", list->data[i]);
    }
    printf("\n");
}

/*
 * 查找顺序表中指定元素的索引
 * list: 指向顺序表的指针
 * value: 要查找的元素值
 * return: 返回元素的索引，若未找到则返回-1
 */
int FindElem(SeqList *list, TemType value)
{
    for (int i = 0; i < list->length; i++)
    {
        if (list->data[i] == value)
        {
            return i; // 找到元素，返回索引
        }
    }
    return -1; // 未找到元素
}

/*
 * 获取顺序表的长度
 * list: 指向顺序表的指针
 * return: 返回顺序表的当前长度
 */
int GetLength(SeqList *list)
{
    return list->length; // 返回当前长度
}

/*
 * 获取顺序表的最大容量
 * list: 指向顺序表的指针
 * return: 返回顺序表的最大容量
 */
int GetMaxSize(SeqList *list)
{
    return list->maxSize; // 返回最大容量
}

/*
 * 判断顺序表是否为空
 * list: 指向顺序表的指针
 * return: 若顺序表为空则返回1，否则返回0
 */
int IsEmpty(SeqList *list)
{
    return list->length == 0; // 若长度为0则为空
}

/*
 * 判断顺序表是否已满
 * list: 指向顺序表的指针
 * return: 若顺序表已满则返回1，否则返回0
 */
int IsFull(SeqList *list)
{
    return list->length == list->maxSize; // 若长度等于最大容量则已满
}

/*
 * 主函数示例
 * 用于测试顺序表的基本操作
 */
void TestSeqList()
{
    SeqList list;
    InitList(&list, 5); // 初始化顺序表，最大容量为5

    InsertTail(&list, 10);
    InsertTail(&list, 20);
    InsertHead(&list, 5);
    PrintList(&list); // 打印顺序表

    DeleteElem(&list, 1); // 删除位置1的元素
    PrintList(&list);     // 打印顺序表

    printf("Element at index 0: %d\n", GetElem(&list, 0));    // 获取位置0的元素
    printf("Index of element 20: %d\n", FindElem(&list, 20)); // 查找元素20的索引

    ClearList(&list); // 清空顺序表
    PrintList(&list); // 打印顺序表

    DestroyList(&list); // 销毁顺序表
}

int main(int argc, char const *argv[])
{
    /* code */
    TestSeqList(); // 测试顺序表的基本操作
    printf("顺序表测试完成。\n");
    return 0;
}
